/**
* @description: 807. 保持城市天际线
* @author hewei
* @date 2022/8/29 14:29
* @version 1.0
*/

public class MaxIncreaseKeepingSkyline {

    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] maxRow = new int[m];
        int[] maxCol = new int[m];
        for (int i = 0; i < m; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < n; j++) {
                max = Math.max(max, grid[i][j]);
            }
            maxRow[i] = max;
        }
        for (int i = 0; i < n; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < m; j++) {
                max = Math.max(max, grid[j][i]);
            }
            maxCol[i] = max;
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans += Math.min(maxCol[j], maxRow[i]) - grid[i][j];
            }
        }
        return ans;
    }
}
